Árbol binario indexado

Un árbol binario indexado o árbol de Fenwick es una estructura de datos que proporciona métodos eficientes para el cálculo y la manipulación de las cantidades de prefijos de una array de valores. Fue propuesto por Boris Ryabko en 1989 ​ con una modificación posterior publicada por el mismo autor en 1992.​ Luego volvió a ser conocida como árbol de Fenwik tras la publicación del artículo de Peter Fenwick en 1994.​ El Fenwick Tree principalmente resuelve el problema de equilibrar la eficiencia de la suma del prefijo con la eficiencia de modificar un elemento. La eficacia de estas operaciones se presenta como una solución de compromiso, (dado que una mayor eficiencia en el cálculo de la suma del prefijo se consigue precalculando los valores, pero una vez que los valores son precalculados, debe volverse a calcular cada vez que ocurra una modificación). Esto haría O(1) las consultas pero las modificaciones serían O(n). El Fenwick Tree hace ambas operaciones en O(log n), donde n es el tamaño del array.

Descripción

Dado un array de elementos, a veces es deseable calcular el total acumulado de los valores hasta un índice de acuerdo con alguna operación binaria asociativa.

El Fenwick Tree proporciona un método para consultar el total acumulado hasta cualquier índice, además de permitir cambios en el array en un índice específico y que las consultas siguientes reflejen dicho cambio.

Aunque los Fenwick Tree son árboles en concepto, en la práctica se implementan usando un array análogo a las implementaciones de un montículo binario.

Idea básica

Como se sabe cada entero puede ser representado como suma de potencias de 2. De la misma manera las frecuencias acumulativas (suma de las posiciones del principio hasta una posición i) pueden ser representadas como suma de subfrecuencias. Esta es la idea básica de esta estructura de datos. Sólo se necesitaría un array (tree) de la misma longitud del array original.

Sea idx cualquier índice del tree y r la posición del último dígito 1 (de izquierda a derecha) en la representación en binario de idx ; entonces tree[idx] es la suma desde el índice ($idx-2^{r}+1$) hasta el índice idx .

Si por ejemplo se quisiera saber la suma hasta 13. Como en binario el 13 se escribe como 1101, podemos calcularlo así:

$\operatorname {sum} (13)=\operatorname {tree} (1101)+\operatorname {tree} (1100)+\operatorname {tree} (1000)$

Pseudocódigo

Método de consulta:

 function Consulta(ind)
      suma := 0
      while ind > 0
          suma := suma + tree[ind]
          ind := ind - (ind & -ind)
      return suma

Método de modificación:

 function Modificar(ind, val)
      while ind < MaxVal
          tree[ind]:= tree[ind]+ val
          ind := ind + (ind & -ind)

Aplicaciones

El Fenwick Tree es muy fácil para manejar un array de suma acumulativa y de este array de suma acumulativa es posible calcular la suma de las frecuencias en un cierto rango en el orden de O (log (n)). Permite hacer este procedimiento además con cualquier operación asociativa. El Fenwick Tree se utiliza para implementar el algoritmo de codificación aritmética.

Véase también

• Árbol de segmento

Enlaces externos

• Tutorial de árbol binario indexado en TopCoder.
• Un artículo de Fenwick Trees en Algorithmist

• Datos: Q1276370
• Multimedia: Fenwick trees / Q1276370